Exercise (Week 8)

Your first task will be to implement the function

onlyUnique :: FilePath -> FilePath -> IO ()

which should define a procedure that: reads the given input file (the first argument), throws away all lines in the file that appear more than once, then writes the remaining (unique) lines to the given output file. The input file should only be read, not changed. Note that the FilePath type is just a type synonym for String. To read files, you can just use the function readFile in this simple exercise; you can find a variety of other file manipulation functions in System.IO, but you won't need them for this problem.

There is a well-known number guessing game where the player attempts to guess a secret integer number that the computer has chosen randomly between 1 and 100.

If the player guesses incorrectly, the only information they receive is whether the secret number is lower or higher than the player's guess.

The player wins if they successfully guess the secret. But if the player fails to guess the secret number in a certain number of turns, they lose.

You will be provided with an implementation of this game in Haskell. You should study the implementation, and the notes below, to make sure that you understand how it works. Your task will be to develop a simple AI which can play this game.

Notes

We define a bunch of data classes to store the game state, the possible outcomes of the game, and the possible feedback responses the player may get (Lower, Higher). This is fairly straightforward.

The first surprise comes when we define the Player data type. Since the game has to support both human and AI player, we will define Player as a type that consists of two monadic callback functions. One of these functions, guess is the one that's called when the player has to make a guess. The other, signalWrong is the function that is used to tell the player whether their last guess was too high (Lower, meaning go lower), or too low (Higher, meaning go higher).

data Player m = Player { guess :: m Int
                       , signalWrong :: Response -> m () 
                       }

We have the m as a type parameter, because different players will need different monads to handle responses. A human player will need the IO monad: to let the player make a guess, we will need a guess function with the type guess :: IO Int (i.e. a procedure that asks the player for a guess, then returns the answer).

The AI will not need to do IO: it can make its `guess` by consulting a data structure that contains its state, and incorporate the `Response` by modifying this data structure. Therefore, an AI player can play using the `State AiState` monad.

The guessing game's main loop, gameLoop, is defined generically so that it works with any monad m, as long as we can provide a Player that acts in that monad. You can play the guessing game yourself in the IO monad with the human player by calling play:

Your task is to define a new player, ai, which plays the game automatically, by acting in the State AiState monad instead of the IO monad:

data AiState =
  AiState {
    lowerBound :: Int,
    upperBound :: Int
  } deriving (Show, Eq)

ai :: Player (State AiState)
ai = Player { guess = aiGuess, signalWrong = aiWrong } where
  aiGuess = ...
  aiWrong = ...

We would like to test that the AI implementation satisfies some properties. Firstly, we would like the ai player never to repeat a guess, that is, the ai player should guess the number in at most 100 guesses. This is implemented in prop_winEventually, which you can run using quickCheck as usual.

A more advanced AI should play optimally: it is known that the game can always be won using 7 guesses. This is implemented in the second test, prop_winsOptimally.